package a.codetop.DP;

import org.junit.Test;

public class 最长公共子序列 {

    public int longestCommonSubsequence (String s1, String s2) {
        //0~i和0~j 的中间任意区间的 最长公共子序列长度
        int[][] dp = new int[s1.length()][s2.length()];

        //先有的公式[i-1]..，后补边界
        dp[0][0]= s1.charAt(0)==s2.charAt(0)?1:0;
        for (int i = 1; i < s1.length(); i++) {
            dp[i][0]= s1.charAt(i)==s2.charAt(0)?1:dp[i-1][0];
        }
        for (int j = 1; j < s2.length(); j++) {
            dp[0][j]= s1.charAt(0)==s2.charAt(j)?1:dp[0][j-1];
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if(s1.charAt(i)!=s2.charAt(j)) dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                else dp[i][j]=dp[i-1][j-1]+1;
            }
        }

        return dp[dp.length-1][dp[0].length-1];
    }

    @Test
    public void test() {
        System.out.println(longestCommonSubsequence("abcde","ace"));
    }
}
